package uba.algo3.tp2.ej2;

import java.util.ArrayList;


public class Ciclo
{
	ArrayList<Rectangulo> rectangulos;
	
	public Ciclo(ArrayList<Valla> recorrido)
	{
		//DIVIDIR EN FIGURAS PEGADAS POR VERTICES!
		rectangulos = dividirEnRectangulos(recorrido);//O(vallas_del_ciclo^2)
	}
	
	public int calcularSuperficie()
	{
		int superficie = 0;
		
		for(Rectangulo r : rectangulos)
		{
			superficie = superficie + r.calcularSuperficie();
		}
		
		return superficie;
	}


	public static ArrayList<Rectangulo> dividirEnRectangulos(ArrayList<Valla> ciclo)
	{
		int sentido,i, index = 0,indexVert = -1;
		Valla vpred = ciclo.get(0),actual,nueva_valla = null, valla_unida = null,unida_con_nueva = null;
		Coordenadas pred,nuevas_coordenadas;
		
		ArrayList<Rectangulo> rect1, rect2;
		ArrayList<Valla> ciclo1 = new ArrayList<Valla>();
		
		if(ciclo.size() == 4)//halle un rectangulo!
		{
			Valla altura,base;
			rect1 = new ArrayList<Rectangulo>();
			if(ciclo.get(0).esVertical())
			{
				altura = ciclo.get(0);
				base = ciclo.get(1);
			}
			else
			{
				altura = ciclo.get(1);
				base = ciclo.get(0);			
			}
			
			
			Rectangulo r = new Rectangulo(altura,base);
			rect1.add(r);
			return rect1;
		}//O(1)

		sentido = vpred.hallarSentido(ciclo.get(1));//O(1)
		
		if(sentido == 1 || sentido == 2)//esto es xq en los llamados recursivos puedo llamarlo con una primera arista en el ciclo que no sea en sentido norte como en la primera llamada
		{
			 pred = vpred.getExtremo2();
		}
		else
		{
			pred = vpred.getExtremo1();
		}//O(1)

		for(i = 1; i <= ciclo.size();i++)//O(vallas_del_ciclo)
		{
			if(i == ciclo.size())
			{
				actual = ciclo.get(0);
			}
			else
			{
				actual = ciclo.get(i);//O(1)
			}

			
			sentido = vpred.hallarSentido(actual);//O(1)
			if(sentido == 1 && actual.voyOeste(pred))//O(1)
			{
				//PRIMERO ME TENGO QUE FIJAR SI NO ESTA PEGADA POR VERTICE OTRA FIGURA
				indexVert = hayFiguraPegadaPorVertice(ciclo,i-1,pred);//O(vallas_del_ciclo)
				
				if(-1 == indexVert)
				{
					index = hallarVallaAlNorte(i,ciclo, vpred);//O(vallas_del_ciclo)

				}
				
				break;
			}
			
			if(sentido == -1 && actual.voyEste(pred))
			{
				
				//PRIMERO ME TENGO QUE FIJAR SI NO ESTA PEGADA POR VERTICE OTRA FIGURA
				indexVert = hayFiguraPegadaPorVertice(ciclo,i-1,pred);

				if(-1 == indexVert)
				{
					index = hallarVallaAlSur(i,ciclo,vpred);
				}
				
				break;
			}
			
			if(sentido == -2 && actual.voySur(pred))
			{
				//PRIMERO ME TENGO QUE FIJAR SI NO ESTA PEGADA POR VERTICE OTRA FIGURA
				indexVert = hayFiguraPegadaPorVertice(ciclo,i-1,pred);

				if(-1 == indexVert)
				{
					index = hallarVallaAlOeste(i,ciclo,vpred);
				

				}	
				
				break;
			}
			
			if(sentido == 2 && actual.voyNorte(pred))
			{
				//PRIMERO ME TENGO QUE FIJAR SI NO ESTA PEGADA POR VERTICE OTRA FIGURA
				indexVert = hayFiguraPegadaPorVertice(ciclo,i-1,pred);

				if(-1 == indexVert)
				{
					index = hallarVallaAlEste(i,ciclo,vpred);
					
				}
				
				break;
				
			}
			pred = actual.obtenerExtremo(pred);
			vpred = actual;

		}
		
		if(indexVert != -1)
		{
			//Quiere decir que tenia una figura pegada por un vertice..divido las figuras
			ciclo1.addAll(ciclo.subList(0,i));
			ciclo1.addAll(ciclo.subList(indexVert+1,ciclo.size()));
			
			ciclo.subList(indexVert+1,ciclo.size()).clear();
			ciclo.subList(0,i).clear();
		}//O(vallas_del_ciclo)
		else
		{
			if(index < i)
			{//Si la valla al norte que encontre esta antes..
				ciclo1 = subdividirCicloAntes(i,index,nueva_valla,valla_unida,ciclo);
			}
			else
			{
				ciclo1 = subdividirCicloDespues(i,index,nueva_valla,valla_unida,ciclo);
			}
		}//O(vallas_del_ciclo)
		
		rect1 = dividirEnRectangulos(ciclo1);
		rect2 = dividirEnRectangulos(ciclo);
		
		rect1.addAll(rect2);//O(rectangulos) = O(vallas_del_ciclo)
		
		return rect1;
	}


	private static ArrayList<Valla> subdividirCicloDespues(int i, int index,
			Valla nueva_valla, Valla valla_unida, ArrayList<Valla> ciclo)
	{
		ArrayList<Valla> ciclo1 = new ArrayList<Valla>();

		ciclo1.addAll(ciclo.subList(0, i));
		if(index+1 <= ciclo.size())
		{	
			ciclo1.addAll(ciclo.subList(index+2,ciclo.size()));
			ciclo.subList(index+2,ciclo.size()).clear();
		}

		ciclo.subList(0,i).clear();
		return ciclo1;
	}

	private static ArrayList<Valla> subdividirCicloAntes(int i, int index,
			Valla nueva_valla, Valla valla_unida, ArrayList<Valla> ciclo)
	{
		ArrayList<Valla> ciclo1 = new ArrayList<Valla>();
		
		ciclo1.addAll(ciclo.subList(0, index+2));
		if(i+1 <= ciclo.size())
		{
			ciclo1.addAll(ciclo.subList(i+2, ciclo.size()));
		}
		
		ciclo.subList(i+2, ciclo.size()).clear();
		ciclo.subList(0, index+2).clear();
		return ciclo1;
	}

	private static int hayFiguraPegadaPorVertice(ArrayList<Valla> ciclo, int index,Coordenadas pred)
	{
		for(int i = index+2; i < ciclo.size(); i++ )
		{
			Valla actual = ciclo.get(i);
			if(actual.getExtremo1().equals(pred) || actual.getExtremo2().equals(pred))
			{
				return i;
			}
		}
		return -1;
	}

	private static int hallarVallaAlEste(int index_prev, ArrayList<Valla> ciclo,
			Valla vpred)
	{
		int x = vpred.getExtremo2().getX();
		int y = vpred.getExtremo1().getY();
		Valla vmenor = null,v;
		int index = -1;
		for(int i = 0; i < ciclo.size();i++)
		{
			v = ciclo.get(i);
			//tengo que buscar la valla que esta al este de vpred, y que esta mas cerca
			if(v.esVertical() && v.getExtremo1().getY() <= y && y <= v.getExtremo2().getY() && v.getExtremo1().getX() > x)
			{
				//quiere decir que si la extiendo, la parte al medio, ahora quiero buscar la que esta mas cerca, la de menor X
				if(vmenor == null)
				{
					vmenor = v;
					index = i;
				}
				else
				{
					if(v.getExtremo1().getX() < vmenor.getExtremo1().getX())
					{
						vmenor = v;
						index = i;
					}
				}
			}
		}
		if(vmenor.getExtremo1().getY() == y || vmenor.getExtremo2().getY() == y)
		{
			//estan a la misma altura, no hay que subdividir la valla
			Valla veste = ciclo.get(index);
			Coordenadas nuevas_coordenadas = new Coordenadas(veste.getExtremo1().getX(),vpred.getExtremo1().getY());
			Valla nueva_valla = new Valla(vpred.getExtremo2(),nuevas_coordenadas,veste.getAltura());
			Valla valla_unida = Valla.unirValla(vpred,nueva_valla);
			
			if(vmenor.getExtremo1().getY() == y)
			{
				
				Valla doble_unida = Valla.unirValla(valla_unida, ciclo.get(index+1));
				if(index_prev < index)//ME PARECE QUE SE PUEDE UNIR!!!
				{
					ciclo.remove(index+1);
					ciclo.remove(index_prev-1);
					ciclo.add(index_prev-1,doble_unida);
					ciclo.add(index_prev,nueva_valla);
				}
				else
				{
					ciclo.remove(index_prev-1);
					ciclo.remove(index+1);
					ciclo.add(index+1,nueva_valla);
					ciclo.add(index+2,doble_unida);
				}
			}
			else
			{
				
				if(index == 0)
				{
					index = ciclo.size();
				}
				
				Valla otra_unida = Valla.unirValla(nueva_valla, ciclo.get(index-1));
				if(index_prev < index)
				{
					ciclo.remove(index-1);
					ciclo.remove(index_prev-1);
					ciclo.add(index_prev-1,valla_unida);
					ciclo.add(index_prev,otra_unida);
				}
				else
				{
					ciclo.remove(index_prev-1);
					ciclo.remove(index-1);
					ciclo.add(index-1,otra_unida);
					ciclo.add(index+2,valla_unida);
				}
				return index-2;
			}

		}
		else
		{
		//subdivido la valla encontrada en la zona que se intersecan
			Valla sub1 = new Valla(vmenor.getExtremo1(), new Coordenadas(vmenor.getExtremo1().getX(),y), vmenor.getAltura());
			Valla sub2 = new Valla(new Coordenadas(vmenor.getExtremo1().getX(),y), vmenor.getExtremo2(),vmenor.getAltura());
			
			ciclo.remove(index);
			ciclo.add(index, sub2);
			ciclo.add(index+1,sub1);
			
			Valla veste = ciclo.get(index);
			Coordenadas nuevas_coordenadas = new Coordenadas(veste.getExtremo1().getX(),vpred.getExtremo1().getY());
			Valla nueva_valla = new Valla(vpred.getExtremo2(),nuevas_coordenadas,veste.getAltura());
			Valla valla_unida = Valla.unirValla(vpred,nueva_valla);
			
			if(index_prev < index)
			{
				ciclo.remove(index_prev-1);
				ciclo.add(index_prev-1, valla_unida);	
				ciclo.add(index_prev, nueva_valla);
			}
			else
			{
				ciclo.remove(index_prev-1);
				ciclo.add(index+1, nueva_valla);
				ciclo.add(index+2, valla_unida);
			}
		}
		
		return index;
	}

	private static int hallarVallaAlOeste(int index_prev, ArrayList<Valla> ciclo,
			Valla vpred)
	{
		int x = vpred.getExtremo1().getX();
		int y = vpred.getExtremo1().getY();
		Valla vmayor = null,v;
		int index = -1;
		for(int i = 0; i < ciclo.size();i++)
		{
			v = ciclo.get(i);
			//tengo que buscar la valla que esta al oeste de vpred, y que esta mas cerca
			if(v.esVertical() && v.getExtremo1().getY() <= y && y <= v.getExtremo2().getY() && v.getExtremo1().getX() < x)
			{
				//quiere decir que si la extiendo, la parte al medio, ahora quiero buscar la que esta mas cerca, la de mayor X
				if(vmayor == null)
				{
					vmayor = v;
					index = i;
				}
				else
				{
					if(v.getExtremo1().getX() > vmayor.getExtremo1().getX())
					{
						vmayor = v;
						index = i;
					}
				}
			}
		}

		if(vmayor.getExtremo1().getY() == y || vmayor.getExtremo2().getY() == y)
		{
			//estan a la misma altura, no hay que subdividir la valla
			Valla voeste = ciclo.get(index);
			Coordenadas nuevas_coordenadas = new Coordenadas(voeste.getExtremo1().getX(),vpred.getExtremo1().getY());
			Valla nueva_valla = new Valla(nuevas_coordenadas, vpred.getExtremo1(),voeste.getAltura());
			Valla valla_unida = Valla.unirValla(vpred,nueva_valla);
			
			if(vmayor.getExtremo2().getY() == y)
			{
				Valla doble_unida = Valla.unirValla(valla_unida, ciclo.get(index+1));
				if(index_prev < index)//ME PARECE QUE SE PUEDE UNIR!!!
				{
					ciclo.remove(index+1);
					ciclo.remove(index_prev-1);
					ciclo.add(index_prev-1,doble_unida);
					ciclo.add(index_prev,nueva_valla);
				}
				else
				{
					ciclo.remove(index_prev-1);
					ciclo.remove(index+1);
					ciclo.add(index+1,nueva_valla);
					ciclo.add(index+2,doble_unida);
				}
			}
			else
			{
				
				if(index == 0)
				{
					index = ciclo.size();
				}
				
				Valla otra_unida = Valla.unirValla(nueva_valla, ciclo.get(index-1));
				if(index_prev < index)
				{
					ciclo.remove(index-1);
					ciclo.remove(index_prev-1);
					ciclo.add(index_prev-1,valla_unida);
					ciclo.add(index_prev,otra_unida);
				}
				else
				{
					ciclo.remove(index_prev-1);
					ciclo.remove(index-1);
					ciclo.add(index-1,otra_unida);
					ciclo.add(index+2,valla_unida);
				}
				return index-2;
			}
		}
		else
		{
			//subdivido la valla encontrada en la zona que se intersecan
			Valla sub1 = new Valla(vmayor.getExtremo1(), new Coordenadas(vmayor.getExtremo1().getX(),y), vmayor.getAltura());
			Valla sub2 = new Valla(new Coordenadas(vmayor.getExtremo1().getX(),y), vmayor.getExtremo2(),vmayor.getAltura());
			
			ciclo.remove(index);
			ciclo.add(index, sub1);
			ciclo.add(index+1,sub2);
			
			Valla voeste = ciclo.get(index);
			Coordenadas nuevas_coordenadas = new Coordenadas(voeste.getExtremo1().getX(),vpred.getExtremo1().getY());
			Valla nueva_valla = new Valla(nuevas_coordenadas, vpred.getExtremo1(),voeste.getAltura());
			Valla valla_unida = Valla.unirValla(vpred,nueva_valla);
			
			if(index_prev < index)
			{
				ciclo.remove(index_prev-1);
				ciclo.add(index_prev-1, valla_unida);	
				ciclo.add(index_prev, nueva_valla);
			}
			else
			{
				ciclo.remove(index_prev);
				ciclo.add(index+1, nueva_valla);	
				ciclo.add(index+2, valla_unida);
			}

		}
		return index;
	}

	private static int hallarVallaAlSur(int index_prev, ArrayList<Valla> ciclo,
			Valla vpred)
	{
		int x = vpred.getExtremo1().getX();
		int y = vpred.getExtremo1().getY();
		Valla vmayor = null,v;
		int index = -1;
		Valla unida_con_nueva;
		for(int i = 0; i < ciclo.size();i++)
		{
			v = ciclo.get(i);
			//tengo que buscar la valla mas alta que este por debajo de vpred, y que ademas vpred la este partiendo al medio en el eje x
			if(!v.esVertical() && v.getExtremo1().getX() <= x && x <= v.getExtremo2().getX() && v.getExtremo1().getY() < y)
			{
				//quiere decir que si la extiendo, la parte al medio, ahora quiero buscar la de mayor altura
				if(vmayor == null)
				{
					vmayor = v;
					index = i;
				}
				else
				{
					if(v.getExtremo1().getY() > vmayor.getExtremo1().getY())
					{
						vmayor = v;
						index = i;
					}
				}
			}
		}
		if(vmayor.getExtremo1().getX() == x || vmayor.getExtremo2().getX() == x)
		{
			Valla vsur = ciclo.get(index);
			Coordenadas nuevas_coordenadas = new Coordenadas(vpred.getExtremo1().getX(),vsur.getExtremo1().getY());
			Valla nueva_valla = new Valla(nuevas_coordenadas, vpred.getExtremo1(),vsur.getAltura());
			unida_con_nueva = Valla.unirValla(vpred,nueva_valla);
			
			//estan a la misma altura, no hay que subdividir la valla
			if(vmayor.getExtremo2().getX() == x)
			{
				if(index == 0)
				{
					index = ciclo.size();
				}
				
				Valla otra_unida = Valla.unirValla(nueva_valla, ciclo.get(index-1));
				if(index_prev < index)
				{
					ciclo.remove(index-1);
					ciclo.remove(index_prev-1);
					ciclo.add(index_prev-1,unida_con_nueva);
					ciclo.add(index_prev,otra_unida);
				}
				else
				{
					ciclo.remove(index_prev-1);
					ciclo.remove(index-1);
					ciclo.add(index-1,otra_unida);
					ciclo.add(index+2,unida_con_nueva);
				}
				
				return index-2;
			}
			else
			{
				
				Valla doble_unida = Valla.unirValla(unida_con_nueva, ciclo.get(index+1));
				if(index_prev < index)
				{
					ciclo.remove(index+1);
					ciclo.remove(index_prev-1);
					ciclo.add(index_prev-1,doble_unida);
					ciclo.add(index_prev,nueva_valla);
				}
				else
				{
					ciclo.remove(index_prev-1);
					ciclo.remove(index+1);
					ciclo.add(index+1,doble_unida);
					ciclo.add(index+2,nueva_valla);
				}
				
			}
			
		}
		else
		{
			//subdivido la valla encontrada en la zona que se intersecan
			Valla sub1 = new Valla(vmayor.getExtremo1(), new Coordenadas(x,vmayor.getExtremo1().getY()), vmayor.getAltura());
			Valla sub2 = new Valla(new Coordenadas(x, vmayor.getExtremo1().getY()), vmayor.getExtremo2(),vmayor.getAltura());
			
			ciclo.remove(index);
			ciclo.add(index, sub2);
			ciclo.add(index+1,sub1);
			
			Valla vsur = ciclo.get(index);
			Coordenadas nuevas_coordenadas = new Coordenadas(vpred.getExtremo1().getX(),vsur.getExtremo1().getY());
			Valla nueva_valla = new Valla(nuevas_coordenadas, vpred.getExtremo1(),vsur.getAltura());
			unida_con_nueva = Valla.unirValla(vpred,nueva_valla);
			
			if(index_prev < index)
			{
				ciclo.remove(index_prev-1);
				ciclo.add(index_prev-1,unida_con_nueva);		
				ciclo.add(index_prev,nueva_valla);
			}
			else
			{
				ciclo.remove(index_prev-1);
				ciclo.add(index+1, nueva_valla);	
				ciclo.add(index+2, unida_con_nueva);
			}

		}
		
		return index;
	}

	private static int hallarVallaAlNorte(int index_prev, ArrayList<Valla> ciclo, Valla vpred)
	{
		int x = vpred.getExtremo1().getX();
		int y = vpred.getExtremo2().getY();
		Valla vmenor = null,v;
		int index = -1;
		for(int i = 0; i<ciclo.size();i++)
		{
			v = ciclo.get(i);
			//tengo que buscar la valla mas baja que este por encima de vpred, y que ademas vpred la este partiendo al medio en el eje x
			if(!v.esVertical() && v.getExtremo1().getX() <= x && x <= v.getExtremo2().getX() && v.getExtremo1().getY() > y)
			{
				//quiere decir que si la extiendo, la parte al medio, ahora quiero buscar la de menor altura
				if(vmenor == null)
				{
					vmenor = v;
					index = i;
				}
				else
				{
					if(v.getExtremo1().getY() < vmenor.getExtremo1().getY())
					{
						vmenor = v;
						index = i;
					}
				}
			}
		}
		
		if(vmenor.getExtremo1().getX() == x || vmenor.getExtremo2().getX() == x)
		{
			Valla vnorte = ciclo.get(index);
			Coordenadas nuevas_coordenadas = new Coordenadas(vpred.getExtremo2().getX(),vnorte.getExtremo1().getY());
			Valla nueva_valla = new Valla(vpred.getExtremo2(),nuevas_coordenadas,vnorte.getAltura());
			Valla valla_unida = Valla.unirValla(vpred,nueva_valla);	
			
			if(vmenor.getExtremo2().getX() == x)
			{
				Valla doble_unida = Valla.unirValla(valla_unida, ciclo.get(index+1));
				if(index_prev < index)//ME PARECE QUE SE PUEDE UNIR!!!
				{
					ciclo.remove(index+1);
					ciclo.remove(index_prev-1);
					ciclo.add(index_prev-1,doble_unida);
					ciclo.add(index_prev,nueva_valla);
				}
				else
				{
					ciclo.remove(index_prev-1);
					ciclo.remove(index+1);
					ciclo.add(index+1,nueva_valla);
					ciclo.add(index+2,doble_unida);
				}
			}
			else
			{
				
				if(index == 0)
				{
					index = ciclo.size();
				}
				
				Valla otra_unida = Valla.unirValla(nueva_valla, ciclo.get(index-1));
				if(index_prev < index)
				{
					ciclo.remove(index-1);
					ciclo.remove(index_prev-1);
					ciclo.add(index_prev-1,valla_unida);
					ciclo.add(index_prev,otra_unida);
				}
				else
				{
					ciclo.remove(index_prev-1);
					ciclo.remove(index-1);
					ciclo.add(index-1,otra_unida);
					ciclo.add(index+2,valla_unida);
				}
				return index-2;
			}
		}
		else
		{
			//subdivido la valla encontrada en la zona que se intersecan
			Valla sub1 = new Valla(vmenor.getExtremo1(), new Coordenadas(x,vmenor.getExtremo1().getY()), vmenor.getAltura());
			Valla sub2 = new Valla(new Coordenadas(x, vmenor.getExtremo1().getY()), vmenor.getExtremo2(),vmenor.getAltura());
			
			ciclo.remove(index);
			ciclo.add(index, sub1);
			ciclo.add(index+1,sub2);
			
			Valla vnorte = ciclo.get(index);
			Coordenadas nuevas_coordenadas = new Coordenadas(vpred.getExtremo2().getX(),vnorte.getExtremo1().getY());
			Valla nueva_valla = new Valla(vpred.getExtremo2(),nuevas_coordenadas,vnorte.getAltura());
			Valla valla_unida = Valla.unirValla(vpred,nueva_valla);	
			
			if(index_prev < index)
			{
				ciclo.remove(index_prev-1);
				ciclo.add(index_prev-1,valla_unida);		
				ciclo.add(index_prev,nueva_valla);
			}
			else
			{
				ciclo.remove(index_prev);
				ciclo.add(index+1, nueva_valla);	
				ciclo.add(index+2, valla_unida);
			}
		}
		
		return index;
	}

	public boolean pertenece(Coordenadas coord)
	{
		for(Rectangulo r : rectangulos)
		{
			if(r.pertenece(coord))
			{
				return true;
			}
		}
		return false;
	}

}
